from leetcode_test import TreeNode


class Solution:
    def lowestCommonAncestor(
        self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
    ) -> "TreeNode":
        if q.val > root.val > p.val or p.val > root.val > q.val:
            return root

        if q.val < root.val and p.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)

        if q.val > root.val and p.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)

        if q.val == root.val or p.val == root.val:
            return root


def test():
    t = TreeNode.create([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5])
    p = TreeNode.create([2])
    q = TreeNode.create([8])
    s = Solution().lowestCommonAncestor(t, p, q)
    print(s)
    assert s == t

